package leetcode.bfs;

import java.util.*;

public class Leet773 {
    public static void main(String[] args) {
        Character.isLetterOrDigit('c');
        int[][] board = new int[][]{{4, 1, 2}, {5, 0, 3}};
        int res = new Leet773().slidingPuzzle(board);
        System.out.println(res);
    }

    //773 滑动谜题
    public int slidingPuzzle(int[][] board) {
        int m=board.length;
        int n=board[0].length;
        String target="123450";
        String str="";
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                str+=board[i][j];
            }
        }
        if(target==str){
            return 0;
        }
        //012
        //345
        int[][] dir=new int[][]{{1,3},{0,2,4},{1,5},{0,4},{1,3,5},{2,4}};
        Queue<String> queue=new LinkedList();
        queue.offer(str);

        List<String> visited=new ArrayList();
        visited.add(str);

        int res=0;
        while(!queue.isEmpty()){
            int size=queue.size();
            for (int i = 0; i < size; i++) {
                String cur=queue.poll();
                if(cur.equals(target)){
                    return res+1;
                }
                int zeroIndex=cur.indexOf('0');
                int[] arr=dir[zeroIndex];
                for (int j = 0; j < arr.length; j++) {
                    String newWord=swap(cur,zeroIndex,arr[j]);

                    if(visited.contains(newWord)){
                        continue;
                    }
                    queue.offer(newWord);
                    visited.add(newWord);
                }
            }
            res++;
        }

        return -1;

    }

    public String swap(String str,int i,int j){
        StringBuilder sb=new StringBuilder(str);
        sb.setCharAt(i,sb.charAt(j));
        sb.setCharAt(j,sb.charAt(i));
        return sb.toString();
    }
}
